/***************************************************
*	FileName    :	eightPuzzle.cpp
*	Description :	
*	Created		:	
*   Compiler	:	g++ -o eightPuzzle -g eightPuzzle.h eightPuzzle.cpp main.cpp	
*	
*	Author		:	Victor, mcvector.gu@gmail.com
*	Company		:	College of Information Technology and Science, Chengdu University Of Technology
******************************************************/
#include "eightPuzzle.h"
void PrioQueue::push(StateNode* in)
{
	//if it is the biggest node
	if(node.empty() || *(node.back())<=*(in))
	{
		node.push_back(in);
	}
	else
	{
		for(int i=0; i<node.size(); i++)
		{
			if(*(in)<=*(node[i]))
			{
				//insert in befor ith element
				node.push_back(node.back());
				for(int j=node.size()-1; j>i; j--)
				{	
					node[j] = node[j-1];
				}
				node[i] = in;
				break;
			}
		}
	}
}

void PrioQueue::pop()
{
	for(int i = 0; i < node.size()-1; i++)
	{
		node[i] = node[i+1];
	}
	node.pop_back();
}
//constructor of the code, 
StateTree::StateTree(vector< vector<int> > initial)
{
	done = false;					//set done to false
	startState = new StateNode(initial);
	//initialize goal state
	goalState = new StateNode(initial);	//since the goal state will changed(or just the initial state), so i initial goalState with this
	creatGoalState();
	getManhattenAndCalRow(startState);
	open.push(startState);

}

//creatGoalState
//debug note: This function is correct
void StateTree::creatGoalState()
{

	/*if sum is odd
	  1 2 3
	  8   4
	  7 6 5
	  if sum is even
	    1 2
	  3 4 5
	  6 7 8
	  *************/
	int sum = 0; 
	//go over vector to calculate sum
	for(int i=0; i<3; i++)
	  for(int j=0; j<3; j++)
	  {
		int l=j;
		for(int k=i; k<3; k++)
		{
		  for(; l<3; l++)
		  {
			  if(startState->state.at(i).at(j) !=0 &&
						  startState->state.at(i).at(j) > startState->state.at(k).at(l) 
						  && startState->state.at(k).at(l) != 0)
				sum++;
		  }
		  l = 0;
		}
	  }
	if((sum%2) != 0)			//if sum is odd
	{
		
		 goalStateType = 0;
		 goalState->state.at(0).at(0) = 1;
		 goalState->state.at(0).at(1) = 2;
		 goalState->state.at(0).at(2) = 3;
		 goalState->state.at(1).at(2) = 4;
		 goalState->state.at(2).at(2) = 5;
		 goalState->state.at(2).at(1) = 6;
		 goalState->state.at(2).at(0) = 7;
		 goalState->state.at(1).at(0) = 8;
		 goalState->state.at(1).at(1) = 0;
	}
	else					//if sum is even
	{
		goalStateType = 1;
		int val = 0;
		for(int i=0; i<3; i++)
		  for(int j=0; j<3; j++)
		  {
			  goalState->state.at(i).at(j) = val;
			  val++;
		  }
	}
}
//getManhattenAndCalRow, 
void StateTree::getManhattenAndCalRow(StateNode* st)
{

	int stepSum = 0;
	if(goalStateType  == 1)			//second type
	{
		for(int i=0; i<3; i++)
		  for(int j=0; j<3; j++)
		  {
			  switch(st->state.at(i).at(j))
			  {
				  case(1): stepSum+= (abs(i-0)+abs(j-1)); break;
				  case(2): stepSum+= (abs(i-0)+abs(j-2)); break;
				  case(3): stepSum+= (abs(i-1)+abs(j-0)); break;
				  case(4): stepSum+= (abs(i-1)+abs(j-1)); break;
				  case(5): stepSum+= (abs(i-1)+abs(j-2)); break;
				  case(6): stepSum+= (abs(i-2)+abs(j-0)); break;
				  case(7): stepSum+= (abs(i-2)+abs(j-1)); break;
				  case(8): stepSum+= (abs(i-2)+abs(j-2)); break;
				  case(0): st->bCal = i; st->bRow = j; break;
				  default: cout<<"Input error, Please input number between 0 to 8\n"; exit(1);
			  }
		  }
	}
	else							//first type
	{
		for(int i=0; i<3; i++)
		  for(int j=0; j<3; j++)
		  {
			  switch(st->state.at(i).at(j))
			  {
				  case(1): stepSum+= (abs(i-0)+abs(j-0)); break;
				  case(2): stepSum+= (abs(i-0)+abs(j-1)); break;
				  case(3): stepSum+= (abs(i-0)+abs(j-2)); break;
				  case(4): stepSum+= (abs(i-1)+abs(j-2)); break;
				  case(5): stepSum+= (abs(i-2)+abs(j-2)); break;
				  case(6): stepSum+= (abs(i-2)+abs(j-1)); break;
				  case(7): stepSum+= (abs(i-2)+abs(j-0)); break;
				  case(8): stepSum+= (abs(i-1)+abs(j-0)); break;
				  case(0): st->bCal = i; st->bRow = j; break;
				  default: cout<<"Input error, Please input number between 0 to 8\n"; exit(1);
			  }
		  }
	}
		
	st->manhatten = stepSum+st->step;
}
//here is moving BLANK  !!!!!!!!
StateNode* StateTree::moveUp(StateNode* preState)
{
	if(preState->bCal == 0)                //if can't move up
	  return 0;
	vector< vector<int> > vec = preState->state;	//tamperory vector to save preState
	//move blank
	vec.at(preState->bCal).at(preState->bRow) = vec.at(preState->bCal-1).at(preState->bRow);
	vec.at(preState->bCal-1).at(preState->bRow) = BLANK;
	//StateNode(vector< vector<int> > vState, StateNode* f, int stp)
	StateNode* nowState = new StateNode(vec,preState,preState->step + 1);
	//go over tree to check the same state
		//if there's a same one
			//move it from close to open
	for(int i = 0; i < open.size(); i++)	//go over open list
	{
		if(nowState->isSameAs(open.at(i))&& open.at(i)<nowState)
		  //found a same one in open list, and the new one is worse than openlist one
		{
			delete nowState;
			return 0;		//there's no need to creat new one
		}
	}
	for(int i=0; i < close.size(); i++)		//go over close list
	{
		if(nowState->isSameAs(close.at(i))&& close.at(i)<nowState)
		  //found a same one in close list, and the new one is worse than openlist one
		{
			delete nowState;
			return 0;	//no need to creat the node
		}
	}
	//else, create the node
	getManhattenAndCalRow(nowState);

	return nowState;

}
StateNode* StateTree::moveDown(StateNode* preState)
{

	if(preState->bCal == 2)                //if can't move down
	  return 0;
	vector< vector<int> > vec = preState->state;	//tamperory vector to save preState
	//move blank
	vec.at(preState->bCal).at(preState->bRow) = vec.at(preState->bCal+1).at(preState->bRow);
	vec.at(preState->bCal+1).at(preState->bRow) = BLANK;
	//StateNode(vector< vector<int> > vState, StateNode* f, int stp)
	StateNode* nowState = new StateNode(vec,preState,preState->step + 1);
	//go over tree to check the same state
		//if there's a same one
			//move it from close to open
	for(int i = 0; i < open.size(); i++)	//go over open list
	{
		if(nowState->isSameAs(open.at(i)) && open.at(i)<nowState)	
		  //found a same one in open list, and the new one is worse than openlist one
		{
			delete nowState;
			return 0;		//there's no need to creat new one
		}
	}
	for(int i=0; i < close.size(); i++)		//go over close list
	{
		if(nowState->isSameAs(close.at(i)) && close.at(i)<nowState)
		  //found a same one in close list, and the new one is worse than openlist one
		{
			delete nowState;
			return 0;	//no need to creat the node
		}
	}
	//else, create the node
	getManhattenAndCalRow(nowState);
	return nowState;

}
StateNode* StateTree::moveLeft(StateNode* preState)
{

	if(preState->bRow == 0)                //if can't move left
	  return 0;
	vector< vector<int> > vec = preState->state;	//tamperory vector to save preState
	//move blank
	vec.at(preState->bCal).at(preState->bRow) = vec.at(preState->bCal).at(preState->bRow-1);
	vec.at(preState->bCal).at(preState->bRow-1) = BLANK; 
	//StateNode(vector< vector<int> > vState, StateNode* f, int stp)
	StateNode* nowState = new StateNode(vec,preState,preState->step + 1);
	//go over tree to check the same state
		//if there's a same one
			//move it from close to open
	for(int i = 0; i < open.size(); i++)	//go over open list
	{
		if(nowState->isSameAs(open.at(i)) && open.at(i)<nowState)	
		  //found a same one in open list, and the new one is worse than openlist one
		{
			delete nowState;
			return 0;		//there's no need to creat new one
		}
	}
	for(int i=0; i < close.size(); i++)		//go over close list
	{
		if(nowState->isSameAs(close.at(i)) && close.at(i)<nowState)
		  //found a same one in close list, and the new one is worse than openlist one
		{
			delete nowState;
			return 0;	//no need to creat the node
		}
	}
	//else, create the node
	getManhattenAndCalRow(nowState);
	return nowState;

}

StateNode* StateTree::moveRight(StateNode* preState)
{

	if(preState->bRow == 2)                //if can't move Right
	  return 0;
	vector< vector<int> > vec = preState->state;	//tamperory vector to save preState
	//move blank
	vec.at(preState->bCal).at(preState->bRow) = vec.at(preState->bCal).at(preState->bRow+1);
	vec.at(preState->bCal).at(preState->bRow+1) = 0;
	//StateNode(vector< vector<int> > vState, StateNode* f, int stp)
	StateNode* nowState = new StateNode(vec,preState,preState->step + 1);
	//go over tree to check the same state
		//if there's a same one
			//move it from close to open
	for(int i = 0; i < open.size(); i++)	//go over open list
	{
		if(nowState->isSameAs(open.at(i)) && open.at(i)<nowState)	
		  //found a same one in open list, and the new one is worse than openlist one
		{
			delete nowState;
			return 0;		//there's no need to creat new one
		}
	}
	for(int i=0; i < close.size(); i++)		//go over close list
	{
		if(nowState->isSameAs(close.at(i)) && close.at(i)<nowState)
		  //found a same one in close list, and the new one is worse than openlist one
		{
			delete nowState;
			return 0;	//no need to creat the node
		}
	}
	//else, create the node
	getManhattenAndCalRow(nowState);
	return nowState;

}
//creatChildren
//this function is used to 
//1.Creat children
//2.move previosu State form open to close
void StateTree::creatChildren()
{
	if(open.isEmpty())			//if open is empty, search failed
	{
		done = true;
		cout<<"No answer!!\n";
		return;
	}
	//get previous State and move it to close
	StateNode* pState = open.top();
	if(pState->isSameAs(goalState))
	{
		//pState is the goal state
		
		done = true;
		//Save the path to solution
		StateNode* NodeOnPath = pState;
		solution.push(pState);
		while(!NodeOnPath->isSameAs(startState))
		{
			solution.push(NodeOnPath = NodeOnPath->father);
		}
		return;
	}
	open.pop();
	close.push_back(pState);
	//cout<<"----------Step: "<<pState->step<<"-----manhattan: "<<pState->manhatten<<"-------------------------------"<<endl;		//debug
	//cout<<*(pState);					//debug
	//move and push new states into open
	StateNode* tempNode;
	if(tempNode = moveUp(pState))
	{
		open.push(tempNode);
	}
	if(tempNode = moveDown(pState))
	{
		open.push(tempNode);
	}	
	if(tempNode = moveLeft(pState))
	{
		open.push(tempNode);
	}
	if(tempNode = moveRight(pState))
	{
		open.push(tempNode);
	}
	//move pState to close
	
}
void StateTree::solve() 
{
	while(!done)
	{
		creatChildren();
	}

}
//print resulj
void StateTree::showResult()
{
	if(solution.empty())
	{
		cout<<"search failed!";
		exit(0);
	}
	cout<<"\n"<<solution.size()-1<<" Steps to reach the goal!\n";
	while(!solution.empty())
	{
		cout<<*(solution.top())<<endl;
		solution.pop();
	}
}
